#include<stdio.h>
#include<stdlib.h>

int ret;

struct node
{    int val;
     struct node *p;
}*first,*cur,*second;

void append(int x)
{   struct node *new=malloc(sizeof(struct node));
    if(new==NULL)
     printf("\n\tMemory allocation error");
    else
    { new->val=x;
      new->p=NULL;
    }
    if(first==NULL)
    {  first=new;
       cur=new;
    }  
    else
    {   cur->p=new;
        cur=new;
    }   
    printf("\n\tElement appended\n");
}//append 

void append2(int x)
{   struct node *new=malloc(sizeof(struct node)),*i,*j;
    if(new==NULL)
     printf("\n\tMemory allocation error");
    else
    { new->val=x;
      new->p=NULL;
    }
    if(second==NULL)
       second=new;
    else
    {   for(i=second;i!=NULL;i=i->p)
           j=i;
        j->p=new;
    }   
}//append2 

void extend(struct node *second)
{   if(second==NULL)
       printf("\n\tThe second list is empty");
    else
    {   struct node *p1;
        for(p1=second;p1!=NULL;p1=p1->p)
        {   struct node *new=malloc(sizeof(struct node));
            if(new==NULL)
               printf("\n\tMemory allocation error");
            else
            {   new->val=p1->val;
                new->p=NULL;
            }
            if(first==NULL)
            {  first=new;
               cur=new;
            }  
            else
            {   cur->p=new;
                cur=new;
            }
        }//for   
    }//else        
    printf("\n\tList Extended\n");
}//extend

void insert(int x,int pos)
{   struct node *new=malloc(sizeof(struct node));
    struct node *p1,*p2=first;
    int ctr=0,flag=0;
    if(new==NULL)
     printf("\n\tMemory allocation error");
    else
    {   new->val=x;
      	new->p=NULL;
        if(first==NULL && (pos==0 || pos==-1))
        {   first=new;
            cur=new;
            flag=1;
        }
        else if(pos==-1)
        {   cur->p=new;
            cur=new;
            flag=1;
        }
        else
        {   for(p1=first;p1!=NULL;p1=p1->p)
            {   if(ctr==pos)
                {   new->p=p1;
                    if(p1==first)
                       first=new;
                    else
                       p2->p=new;
                    printf("\n\tElement inserted");
                    flag=1;
                    break;
                }
                p2=p1;
                ctr++;
            }//for
         }//else
         if(flag==0)
           printf("\n\tInvalid position");
    }//else
}//insert

void remve(int x)
{   struct node *p1,*p2;
    int flag=0;
    for(p1=first;p1!=NULL;p1=p1->p)
    {   if(p1->val==x)
        {   if(p1!=first)
               p2->p=p1->p;
            else
               first=p1->p;
            p2=p1;
            free(p2);
            flag=1;
            printf("\n\tElement removed");
            break;
        }
        p2=p1;
    }//for
    if(flag==0)
       printf("\n\tValue not found");
}//remove

int pop(int pos)
{   struct node *p1,*p2;
    int ctr=0,flag=0,pop;
    if(pos==-1)
    {   for(p1=first;p1!=NULL;p1=p1->p)
        {   if(p1==cur)
            {   if(p1!=first)
                   p2->p=NULL;
                else
                   first=p1->p;
                cur=p2;   
                p2=p1;
                pop=p2->val;
                free(p2);
                flag=1;
                break;   
             }
             p2=p1;
        }
    }//if
    else
    {   for(p1=first;p1!=NULL;p1=p1->p)
        {   if(ctr==pos)
            {   if(p1!=first)
                   p2->p=p1->p;
                else
                   first=p1->p;
                if(p1==cur)
                   cur=p2;
                p2=p1;
                pop=p2->val;
                free(p2);
                flag=1;
                break;   
            }
            p2=p1;
            ctr++;
       }//for 
    }//else
    if(flag==1)
    {   printf("\n\tElement removed");
        ret=1;
        return pop;
    }
    if(flag==0)
    {   printf("\n\tInvalid position");
        ret=0;
    }
}//pop

int indx(int x)
{   struct node *p1;
    int ctr=0,flag=0;
    for(p1=first;p1!=NULL;p1=p1->p)
    {   if(p1->val==x)
        {   flag=1;
            break;
        }
        ctr++;
    }//for
    if(flag==0)
    {   printf("\n\tValue not found");
        ret=0;
    }
    else
    {   ret=1;
        return ctr;
    }
}//index

int count(int x)
{   struct node *p1;
    int ctr=0;
    for(p1=first;p1!=NULL;p1=p1->p)
    {   if(p1->val==x)
           ctr++;
    }//for
    return ctr;
}//count

void reverse()
{    struct node *temp,*temp1,*p1;
     temp=NULL;
     for(p1=first;p1!=NULL;p1=temp1)
     {  temp1=p1->p;
        p1->p=temp;
        temp=p1;       
     } 
     first=temp;
}//reverse

void sort(int x)
{   struct node *p1,*pos,*p2;
    int temp;
    for(p1=first;p1!=NULL;p1=p1->p)
    {	pos=p1;
        for(p2=p1;p2!=NULL;p2=p2->p)
        {   if(pos->val>p2->val)
            {   pos=p2;
            }
        }
        temp=p1->val;
        p1->val=pos->val;
        pos->val=temp;
    }
    if(x==1)
       reverse();
}//sort

void display()
{ struct node *p1;
  printf("\n\t[");
  for(p1=first;p1!=NULL;p1=p1->p)
  {   if(p1!=first)
        printf(", ");   
      printf("%d",p1->val);
  }
  printf("]\n");
}//display
 
void main()
{     first==NULL;
      int ch,x;
      do
      {   printf("\n\n\tPython list in C");
          printf("\n\n\t1)Append an element");
          printf("\n\t2)Extend the list");
          printf("\n\t3)Insert anywhere in list");
          printf("\n\t4)Remove an element");
          printf("\n\t5)Pop an element");
          printf("\n\t6)Search 1st position of an element");
          printf("\n\t7)Number of occurences");
          printf("\n\t8)Sort the list"); 
          printf("\n\t9)Reverse the list");
          printf("\n\t10)Exit");
          printf("\n\n\tEnter choice:");
          scanf("%d",&ch);
          switch(ch)
          {   case 1:{   printf("\n\tEnter value to be inserted:");
                         scanf("%d",&x);
                         append(x);
                         display();
                         break;
                     }
              case 2:{  for(;second!=NULL;second=second->p)
                        {   struct node *p2;
                            p2=second;
                            free(p2);
                        }
                        second==NULL;
                        int i,num;
                     	printf("\n\tHow many elements you want to add:");
                     	scanf("%d",&num);
                     	for(i=1;i<=num;i++)
                     	{   printf("\n\tEnter value:");
                            scanf("%d",&x);
                            append2(x);
                     	}
                        extend(second);
                        display();
                        break; 
                     }
              case 3:{   int pos;
                         printf("\n\tEnter value:");
      	                 scanf("%d",&x);
      		         printf("\n\tEnter position to be inserted(0 for beginning,-1 for end):");
                         scanf("%d",&pos);
                         insert(x,pos);       
                         display();
                         break;
                     }
              case 4:{   if(first==NULL)
                            printf("\n\tList is empty");
                         else
                         {   printf("\n\tEnter value:");
      	                     scanf("%d",&x);
      		             remve(x);       
                             display();
                         }
                         break;
                     }
              case 5:{   if(first==NULL)
                            printf("\n\tList is empty");
                         else
                         {   int v;
                             printf("\n\tEnter the  position (0 for 1st element,-1 for no entry):");
                             scanf("%d",&x);
                             v=pop(x);
                             if(ret==1)
                                printf("\n\tThe value popped is=%d",v);
                             display();
                         }
                         break;
                     }
              case 6:{   if(first==NULL)
                            printf("\n\tList is empty");
                          else
                          {  int v;
                             printf("\n\tEnter value:");
      	                     scanf("%d",&x);
      		             v=indx(x); 
                             if(ret==1)      
                                printf("\n\tThe first occurence of element is at position %d",v);
                         }
                         break;
                     }
              case 7:{   if(first==NULL)
                            printf("\n\tList is empty");
                          else
                         {   int v;
                             printf("\n\tEnter value:");
      	                     scanf("%d",&x);
      		             v=count(x);       
                             printf("\n\tNumber of occurences of %d is %d",x,v);
                          }
                          break;                    
                     }
              case 8:{   if(first==NULL)
                            printf("\n\tList is empty");
                          else
                          {   printf("\n\tEnter 0 for ascending or 1 for descending:");
                             scanf("%d",&x);
                             if(x!=0 && x!=1)
                                printf("\n\tInvalid input");
                             else
                             {   sort(x);       
                                 printf("\n\tDisplaying the list in sorted order...\n");
                                 display();
                             }
                          }//else
                          break;
                     }       
              case 9:{   if(first==NULL)
                            printf("\n\tList is empty");
                          else
                          {   reverse();       
                              printf("\n\tDisplaying the list in reverse order...\n");
                              display();
                          }
                          break;
                     }
             case 10:{   printf("\nQuitting...\n");
                         exit(1);
                         break;
                     }
             default:printf("\n\tInvalid choice...");
          }//switch
      }while(ch!=10);             
}//main


